对 Python 列表常见操作的理解

写这篇文章的原因是前几天做了一道面试题，问题大致是这样的：

l = [1, 2, 3, 4, 5]

l.insert(1, 6)
和
l.append(6)
 
的时间复杂度分表是什么

我理所应当的认为，Python 列表的内部实现应该是一个链表，而链表的插入和追加操作应该都是 O(1)，但今天看到一篇文章原文地址，发现并不是我认为的那样。

Python 在 C 实现中，存储数据的部分是一块连续的内存数组，不过这个数组里存放的也是指针，指向具体的元素，并且会在 结构体 中记录元素的实际个数，结构体如下。

typedef struct {
    # 列表元素的长度
    int ob_size; 
    # 真正存放列表元素容器的指针，list[0] 就是 ob_item[0]
    PyObject **ob_item;
    # 当前列表可容纳的元素大小
    Py_ssize_t allocated;
} PyListObject;

当追加新元素的时候，可以直接通过 ob_item[ob_size]=n 来完成，所以时间复杂度为 O(1)。

在插入元素时，操作如下，将要插入位置下方的所有元素向下移动一个位置，然后将要插入位置指向我们插入的元素即可。所以时间复杂度其实是 O(n)。

（以上都没有考虑 allocated 分配的情况）

再来看下 pop 这个操作，pop 时只需将 ob_size 减一即可，所以时间复杂的也是 O(1)。

remove 就没这么简单了，需要先通过遍历的方式找到要移除的元素，然后将找到的位置到最后一个有效位置这之间的指针都指向其 next 指向的元素（也就是 ob_item[i]=ob_item[i+1]），然后 ob_size-1，所以时间复杂度也为 O(n)

这就是我对 list 几个常见操作的理解，如有错误之处请通过邮件方式指出: jiapan.china#gmail.com